1166C - A Tale of Two Lands - CodeForces Solution


binary search sortings two pointers *1500

Please click on ads to support us..

Python Code:

input()
a=sorted(map(abs,map(int,input().split())))
r=i=j=0
while i<len(a):
 while 2*a[j]<a[i]:j+=1
 r+=i-j;i+=1
print(r)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define sst string
#define pb push_back
#define maxco 100000+5
#define lld long double
#define cha ios_base::sync_with_stdio(false);
#define ffl cout.flush();
#define phi acos(-1)
#define mod 1000000000
#define mp make_pair
#define pqpair priority_queue<pair<ll,ll> ,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
pqpair pq;
#define INF 1000000000
#define MAXN 100009
#define pi pair<ll,ll>
ll n,m,k,s;
ll a[200009];
vector<ll> vec[100009];
ll vis[100009];
bool cur[100009];
int main(){
    cha
    ll n;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        a[i]=abs(a[i]);
    }
    sort(a+1,a+n+1);
    ll ans=0;
    for(ll i=1;i<n;i++){
        ll lb=lower_bound(a+1, a+n+1, 2*a[i]+1)-a;
        if(lb==n+1){
            lb--;
        }
        while(a[lb]>2*a[i]){
            lb--;
        }
        ans+=lb-i;
    }
    cout<<ans;
}


Comments

Submit
0 Comments
More Questions

780C - Andryusha and Colored Balloons
1153A - Serval and Bus
1487C - Minimum Ties
1136A - Nastya Is Reading a Book
1353B - Two Arrays And Swaps
1490E - Accidental Victory
1335A - Candies and Two Sisters
96B - Lucky Numbers (easy)
1151B - Dima and a Bad XOR
1435B - A New Technique
1633A - Div 7
268A - Games
1062B - Math
1294C - Product of Three Numbers
749A - Bachgold Problem
1486B - Eastern Exhibition
1363A - Odd Selection
131B - Opposites Attract
490C - Hacking Cypher
158B - Taxi
41C - Email address
1373D - Maximum Sum on Even Positions
1574C - Slay the Dragon
621A - Wet Shark and Odd and Even
1395A - Boboniu Likes to Color Balls
1637C - Andrew and Stones
1334B - Middle Class
260C - Balls and Boxes
1554A - Cherry
11B - Jumping Jack